Conventionally, various techniques for retrieving similar images have been proposed. As the most popular example, a method of giving keywords to images, and conducting image retrieval based on this keyword is known. Although similar images can be retrieved with high precision, in this method, the user must append keywords to each image. Furthermore, the user must manually select images without keywords, resulting in poor usability. For this reason, in terms of improvement of the usability, image feature amounts are automatically extracted from images, and similar images are retrieved using the image feature amounts.
As a method of extracting image feature amounts from images, and retrieving similar images using the extracted image feature amounts, a method of using color information as image feature amounts predominates. Most of these methods conduct retrieves using image feature amounts such as the RGB ratio, calculated by taking a histogram associated with color information, combinations of colors which frequently appear in images, and the like. However, in case of similar image retrieval based on such a method, since position information of a color is lost, high retrieval precision cannot be expected.
Hence, recently, as described in, e.g., Japanese Patent Laid-Open No. 8-249349, a method of dividing an image into a plurality of blocks, and making pattern matching using respective image feature amounts (representative colors) to retrieve for similar images using the position information of colors has been proposed.
Furthermore, Japanese Patent Laid-Open No. 11-288418(U.S. Pat. No. 6,584,223) proposes, as a similar image retrieval method that considers an array of image feature amounts, a method of specifying a similar line array by performing only matching for respective lines and making matching for respective sequences by re-using the similar line array to calculate a similarity.
However, in case of the similar image retrieval method disclosed in Japanese Patent Laid-Open No. 8-249349, distances between image feature amounts must be calculated for respective blocks between two images which are to undergo matching, resulting in huge computation volumes. Calculations are further complicated when three representative colors are used as image feature amounts, i.e., R, G, and B data.
Since comparison is made using image feature amounts themselves extracted from the images, high comparison precision is assured. However, similar image retrieval is not possible when the angle of an image has changed or when an object position has changed. Hence, this method is not suitable for similar image retrieves such as so-called “natural images”.
On the other hand, in case of the similar image retrieval method disclosed in Japanese Patent Laid-Open No. 11-288418, since a similar line array is specified without any matching for respective lines, the computation volume can be reduced compared to Japanese Patent Laid-Open No. 8-249349. However, as in Japanese Patent Laid-Open No. 8-249349, when a so-called “natural image” is selected as an object, a similar line array cannot be normally specified. As a result, the similarity precision drops. With this method, when a similar line array is not normally specified, the positional relationship between the query and test images cannot be correctly extracted.
Based on such background, it is demanded to implement so-called robust similar image retrieval which can conduct similar image retrieves with ambiguity that can absorb differences even when the image angle has changed, when the object position has changed, or when image feature amounts have some differences due to a change in photographing condition.